package 力扣._76_最小覆盖子串;

class Solution {
    public String minWindow(String s, String t) {
        int[] t_total = new int[256];
        int[] n_total = new int[256];// 当前窗口内的
        int[] avail_total = new int[256];// t中是否出现该字符
        int n = t.length();
        int m = s.length();

        String result = ""; //最终结果

        for (int i = 0; i < n; i++) {
            t_total[t.charAt(i)]++;
            avail_total[t.charAt(i)] = 1;
        }
        int l = 0, r = 0;   // s[l,..,r-1] 不包含r
        int j = 0;
        while (j < m) {
            char c_l = s.charAt(l);
            char c_n = s.charAt(j);

            if (l == r) {   //窗口为空
                if (t_total[c_n] == 0) {// 当前要加入的不在目标序列内
                    l++;
                    r++;
                } else {
                    r++;
                    n_total[c_n]++;
                }
                j++;
            } else {
                // 当前窗口最左侧字符不是目标字符，或者是数量大于要求数量，则可将其从窗口中移除
                if (t_total[c_l] == 0 || n_total[c_l] > t_total[c_l]) {
                    n_total[c_l]--;
                    l++;

                } else {
                    r++;
                    n_total[c_n]++;
                    j++;
                }
            }

            // 比较窗口内的字符串
            int i = 0;
            for (i = 0; i < 256; i++) {
                if (avail_total[i] == 1 && t_total[i] > n_total[i])
                    break;
            }
            // 匹配成功
            if (i == 256) {
                if (result.length() == 0)
                    result = s.substring(l, r);
                else if (r - l< result.length())
                    result = s.substring(l, r);

                // 继续找更短的
                n_total[c_l]--;
                l++;
            }


        }
        return result;


    }

    public static void main(String[] args) {
//        String s = new Solution().minWindow("ADOBECODEBANC", "ABC");
        String s = new Solution().minWindow("bdab", "ab");
        System.out.println(s);
    }
}